package com.cll.learn.stage10.sort;

import java.util.Arrays;

/**
 * 描述信息:
 * 快速排序
 * @author CLL
 * @version 1.0
 * @date 2021/5/14 10:45
 */
public class QuickSort {

    private static void sort(int[] arr, int start, int end) {


        if (start < end) {
            // 声明比较基准值
            int baseValue = arr[start];
            // 定义比较范围
            int i = start, j = end;
            while (i < j) {
                // 大于基准值，不需要进行交换，将后指针向前移动
                while (i < j && arr[j] >= baseValue) {
                    j--;
                }

                // 这个时候，j位置的值已经小于基准值，所以需要进行交换
                if (i < j) {
                    // 第一次到这里的时候，i等于0，baseValue中存放的就是位置i对应的值，所以可以直接覆盖
                    arr[i] = arr[j];
//                    i++;
                }


                while (i < j && arr[i] < baseValue) {
                    i++;
                }

                // 走到这里说明，当前值已经大于基准值
                if (i < j) {
                    arr[j] = arr[i];
                    // j这个时候存放的值肯定是大于基准值的，所以不需要进行比较
//                    j--;
                }
            }
            //
            arr[i] = baseValue;
            sort(arr, start, i-1);
            sort(arr, i+1, end);
        }

    }

    private static void sort2(int[] arr, int start, int end) {
        if (start < end) {
            int i = start, j = end, baseValue = arr[start];
            while (i < j) {
                while (i < j && arr[j] >= baseValue) {
                    j--;
                }

                if (i < j) {
                    arr[i++] = arr[j];
                }

                while (i < j && arr[i] < baseValue) {
                    i++;
                }

                if (i < j) {
                    arr[j] = arr[i];
                }
            }

            arr[i] = baseValue;
            sort2(arr, start, i - 1);
            sort2(arr, i + 1, end);
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{6,37,2,1,9,4,3,2,89,5,7};
        sort2(array, 0, array.length-1);
        System.out.println("result = " + Arrays.toString(array));
    }
}
